//
// Description: 162. 寻找峰值
// Created by Loading on 2021/9/15.
//

#include <bits/stdc++.h>

using namespace std;

/* 二分，O(logn) */
int findPeakElement(vector<int> &nums) {
    int n = nums.size();
    // 一个元素
    if (n == 1) {
        return 0;
    }
    // 左侧特判
    if (nums[0] > nums[1]) {
        return 0;
    }
    // 右侧特判
    if (nums[n - 1] > nums[n - 2]) {
        return n - 1;
    }

    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (mid > 0 && mid < n - 1 && nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
            return mid;
        } else if (mid < n - 1 && nums[mid] < nums[mid + 1]) {// 峰值在右侧
            l = mid + 1;
        } else if (mid > 0 && nums[mid] < nums[mid - 1]) {// 峰值在左侧
            r = mid - 1;
        }
    }

    return -1;
}

int main() {
    vector<int> nums = {1, 2, 1, 3, 5, 6, 4};
    int res = findPeakElement(nums);
    cout << res << endl;

    return 0;
}